package code.oldCode.feishuSpecializedTraining.list;

import utils.ListNode;

public class MyList {
    // 203. 移除链表元素
    public ListNode removeElements(ListNode head, int val) {
        ListNode origin = new ListNode();
        origin.next = head;
        ListNode p = head;
        ListNode pre = origin;
        while (p != null) {
            if (p.val == val) {
                pre.next = p.next;
            } else {
                pre = p;
            }
            p = p.next;
        }
        return origin.next;
    }

    // 206. 反转链表
    public ListNode reverseList(ListNode head) {
        ListNode right = head;
        ListNode left = null;
        while (right != null) {
            ListNode temp = right.next;
            right.next = left;
            left = right;
            right = temp;
        }
        return left;
    }

    // 24. 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        ListNode headPre = new ListNode();
        headPre.next = head;
        ListNode p = headPre;
        boolean isFirst = true;
        while (p.next != null && p.next.next != null) {
            ListNode left = p.next;
            ListNode right = p.next.next;
            left.next = right.next;
            right.next = left;
            if (isFirst) {
                isFirst = false;
                head = right;
            }
            p.next = right;
            p = left;
        }
        return head;
    }
}

// 707. 设计链表
class MyLinkedList {

    // 头结点前的节点，即第一个节点之前的节点作为头结点
    MyListNode firstNodePre;

    public MyLinkedList() {
        firstNodePre = new MyListNode();
    }

    public int get(int index) {
        MyListNode indexNode = firstNodePre;
        for (int i = 0; i <= index; i++) {
            if (indexNode.next == null)
                return -1;
            indexNode = indexNode.next;
        }
        return indexNode.val;
    }

    public void addAtHead(int val) {
        MyListNode newNode = new MyListNode(val);
        MyListNode temp = firstNodePre.next;
        firstNodePre.next = newNode;
        newNode.next = temp;
    }

    public void addAtTail(int val) {
        MyListNode lastNode = firstNodePre;
        while (lastNode.next != null) {
            lastNode = lastNode.next;
        }
        lastNode.next = new MyListNode(val);
    }

    public void addAtIndex(int index, int val) {
        MyListNode newNode = new MyListNode(val);
        MyListNode indexNodePre = firstNodePre;
        for (int i = 0; i < index; i++) {
            if (indexNodePre.next == null)
                return;
            indexNodePre = indexNodePre.next;
        }
        MyListNode temp = indexNodePre.next;
        indexNodePre.next = newNode;
        newNode.next = temp;
    }

    public void deleteAtIndex(int index) {
        MyListNode indexNodePre = firstNodePre;
        for (int i = 0; i < index; i++) {
            if (indexNodePre.next == null)
                return;
            indexNodePre = indexNodePre.next;
        }
        if (indexNodePre.next == null)
            return;
        indexNodePre.next = indexNodePre.next.next;
    }
}

class MyListNode {
    int val;
    MyListNode next;
    MyListNode() {
        this.val = -1;
        this.next = null;
    }
    MyListNode(int val) {
        this.val = val;
        this.next = null;
    }
    MyListNode(int val, MyListNode next) {
        this.next = next;
        this.val = val;
    }
}